package algorithm;

public class QuickSort {
    /**
     * 以左端点为参照基准
     * @param array
     * @param left
     * @param right
     */
    public void quickSort(Integer[] array, Integer left, Integer right){
        if(left >= right){
            return ;
        }
        Integer baseVal = array[left];
        Integer lk= left , rk = right;
        while(lk < rk){
            while(array[rk] >= baseVal && rk > lk){
                rk --;
            }
            if(rk > lk){
                array[lk] = array[rk];
            }

            while(array[lk] <= baseVal && lk < rk){
                lk ++;
            }
            if(lk < rk){
                array[rk] = array[lk];
            }
        }
        array[lk] = baseVal;
        quickSort(array,left,lk-1);
        quickSort(array,lk + 1,right);
    }

    /**
     * 以右端点为参照基准
     * @param array
     * @param left
     * @param right
     */
    public void quickSort2(Integer[] array, Integer left, Integer right){
        if(left >= right){
            return ;
        }
        Integer baseVal = array[right];
        Integer lk= left , rk = right;
        while(lk < rk){
            while(array[lk] <= baseVal && lk < rk){
                lk ++;
            }
            if(lk < rk){
                array[rk] = array[lk];
            }

            while(array[rk] >= baseVal && rk > lk){
                rk --;
            }
            if(rk > lk){
                array[lk] = array[rk];
            }
        }
        array[lk] = baseVal;
        quickSort(array,left,lk-1);
        quickSort(array,lk + 1,right);
    }
}
